# 给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。
#  子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。
#  如果 (x1, y1, x2, y2) 和 (x1', y1', x2', y2') 两个子矩阵中部分坐标不同（如：x1 != x1'），那么这两个子矩阵也不同。
#
#  示例 1：
# 输入：matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
# 输出：4
# 解释：四个只含 0 的 1x1 子矩阵。
#
#  示例 2：
# 输入：matrix = [[1,-1],[-1,1]], target = 0
# 输出：5
# 解释：两个 1x2 子矩阵，加上两个 2x1 子矩阵，再加上一个 2x2 子矩阵。
#
#  示例 3：
# 输入：matrix = [[904]], target = 0
# 输出：0
from collections import Counter
from typing import List


class Solution:
    def numSubmatrixSumTarget2(self, matrix: List[List[int]], target: int) -> int:
        """
        前缀和 + 哈希表
        枚举两列之间(上下界分别记为 i1, i2)的列前缀和数组 tmpColSum
            则：tmpColSum[j] = sum(matrix[i][j])  其中 i1 <= i <= i2
            所以 以 (i1, j1)为左上角, (i2, j2)为右下角的矩形和可以表示为
            regionSum = sum(tmpColSum[0:j + 1]) - sum(tmpColSum[0:i])
        :param matrix:
        :param target:
        :return:
        """
        m, n, res = len(matrix), len(matrix[0]), 0

        def subarraySum(nums: List[int], t: int) -> int:
            mp = Counter([0])
            count = preSum = 0
            for x in nums:
                preSum += x
                if preSum - t in mp:
                    count += mp[preSum - t]
                mp[preSum] += 1
            return count

        for i1 in range(m):
            tmpRow = [0] * n  # tmpRow[j] 表示 从 i1 到 i2 的第 j 列的和
            for i2 in range(i1, m):
                for j in range(n):
                    tmpRow[j] += matrix[i2][j]
                res += subarraySum(tmpRow, target)
        return res

    def numSubmatrixSumTarget1(self, matrix: List[List[int]], target: int) -> int:
        """
        暴力法(超时)
        :param matrix:
        :param target:
        :return:
        """
        def getSubSum(x1: int, y1: int, x2: int, y2: int) -> int:
            sumRes = 0
            for i in range(x1, x2 + 1):
                for j in range(y1, y2 + 1):
                    sumRes += matrix[i][j]
            return sumRes
        m, n, res = len(matrix), len(matrix[0]), 0
        for x2 in range(m):
            for y2 in range(n):
                for x1 in range(x2 + 1):
                    for y1 in range(y2 + 1):
                        if getSubSum(x1, y1, x2, y2) == target:
                            res += 1
        return res

    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
        return self.numSubmatrixSumTarget2(matrix, target)


if __name__ == '__main__':
    matrix, target = [[0, 1, 0], [1, 1, 1], [0, 1, 0]], 0
    # matrix, target = [[1, -1], [-1, 1]], 0
    print(Solution().numSubmatrixSumTarget(matrix, target))
